#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// util
struct ufs
{
	vector<int> par;
	ufs(int N=0)
		: par(N, -1)
	{
	}

	int get_ans(int i)
	{
		if(par[i]==-1)
			return i;
		int& ret=par[i];
		return ret=get_ans(ret);
	}

	bool same(int x, int y)
	{ return get_ans(x)==get_ans(y); }

	void union_xy(int x, int y)
	{
		x=get_ans(x);
		y=get_ans(y);
		if(x!=y)
			par[x]=y;
	}
};

// typedef
struct Edge{int s, e, l;};
bool comp_len(const Edge& e1, const Edge& e2){ return e1.l < e2.l; }

typedef vector<Edge> EdgeList;

void MST(EdgeList& g, EdgeList& mst)
{
	// number of nodes
	int N=0;
	for(int i=0;i<g.size();i++)
		N=max(N, max(g[i].s, g[i].e));
	N++;

	// compute
	mst.resize(0);
	ufs u(N);

	sort(g.begin(), g.end(), comp_len);
	for(int i=0;i<g.size();i++)
	{
		if(!u.same(g[i].s, g[i].e))
		{
			u.union_xy(g[i].s, g[i].e);
			mst.push_back(g[i]);
		}
	}
}

int main()
{
	Edge ga[]=
	{
		0,1,3,
		0,2,4,
		1,2,2
	};
	EdgeList g(ga, ga+sizeof(ga)/sizeof(ga[0])), mst;
	MST(g, mst);

	return 0;
}